#include <stdio.h>
#include <stdlib.h>
#define NAMESIZE 2
#define MAXMAPSIZE 16

typedef struct{                 //The structure discribing a single Land (or State), with                           
	int number;                    //the serial number of a land, for further usage.
	char name[NAMESIZE];           //the name of a land, usually as abbr. such as: CA stands for California.
	int color;                     //the color of a land, "0" stands for uncolored.
	} LandItem;
	
	
typedef struct {                      //The 'library' of the map that will be colored, which dontains the basic properties.
	int mapsize;                        
	LandItem *land[MAXMAPSIZE];          //Land are the items of a Map.
	int matrix[MAXMAPSIZE][MAXMAPSIZE]; //The matrix showing boundaries between/among lands.
	} MapLib;
	

int isFinish(MapLib *sample) {        //Detecting whether the coloring is finish.
	int i = 0;
	while (i<sample->mapsize) {
		if (sample->land[i]->color==0) {
			return 0;
			}
		i++;
		}
	return 1;
	}
	
//As in textbook, detecting whether any land with current color that is adjacent to the current land.
int notAdjWith (int color, LandItem *sample_land, MapLib *sample_map ) {  
	int i = 0;
	while (i<=sample_map->mapsize) {
			if (sample_map->land[i]->color==color) {     //of current color
				if (sample_map->matrix[sample_land->number][i]==1) {   //if it is adjacent to current land.
					return 0;
					}
				}
		i++;
		}
	return 1;
	}

int colorUp (MapLib *sample) {
	int i=0;
	int color = 0;
	while (!isFinish(sample)) {
		color++;
		while (i<=sample->mapsize) {
			if (notAdjWith(color, sample->land[i], sample)) { 
				sample->land[i]->color=color;  //If no adjacent-same-color land found, then color it.
				}
			i++;
			}
		}
	if (isFinish(sample)) return 1;  //detecting if all the land are colored.
	else return 0;
	}

MapLib generateMap (char landlist[MAXMAPSIZE][NAMESIZE], int matrix[MAXMAPSIZE][MAXMAPSIZE], int mapsize) {
	int i=0,j=0;
    MapLib *map;
	for(i=0;i<mapsize;i++) {
  	map->land[i]->number=i;
  	for (j=0;j<NAMESIZE;j++) {
  		map->land[i]->name[j]=landlist[i][j];
  		}
  	map->land[i]->color=0;        //Initial color should be 0.
  	}
  	
	for(i=0;i<mapsize;i++) {
  	for (j=0;j<i;j++) {
  		if (matrix[i][j]!=0&&matrix[i][j]!=1) {
  			printf ("Illegal matrix input.");
  			}
  		map->matrix[i][j]=matrix[i][j];
  		map->matrix[j][i]=matrix[i][j]; //Then one can just input half matrices.
  		}
  	}
  	return *map;
	}

int main()
{
	FILE *fr;
	FILE *fr_m;
	fr = fopen("landlist.dat","rt");
	fr_m = fopen("matrix.dat","rt");
	int mapsize=MAXMAPSIZE;
	MapLib *map;
	char landlist[16][2];
	int matrix[16][16];
//Input the land list
	int i,j;
	char separate;
	for(i=0;i<mapsize&&separate!=EOF;i++) {   //Input file contains lands' name separated by one byte.
  	for (j=0;j<NAMESIZE;j++) {
  		landlist[i][j]=fgetc(fr);
  		}
 		separate=fgetc(fr);
  	}
	for(i=0;i<mapsize;i++) {   //Input file contains the matrix.
  	for (j=0;j<mapsize;j++) {
  		matrix[i][j]=0;
  		}
  	}
	for(i=0;i<mapsize;i++) {   //Input file contains the matrix.
  	for (j=0;j<=i;j++) {
  		matrix[i][j]=fgetc(fr_m)-'0';
 		matrix[j][i]=matrix[i][j];
  		}
 	char temp=fgetc(fr_m);	
 	if (temp=="\n") continue;
  	}
  	
	if(!generateMap(landlist,matrix,map,mapsize)) 
  printf("Cannot generate map!");
	map = generateMap(landlist,matrix,mapsize);
	
		for(i=0;i<mapsize;i++) {   //Input file contains the matrix.
  	for (j=0;j<mapsize;j++) {
  		printf("%d",matrix[i][j]);
  		}
  		printf("\n");
  	}
  	
  system("PAUSE");	
  return 0;
}

